#include "../_share/release.hpp"
#include "../_share/comparator.hpp"
#include <iostream>
#include <stack>
#include <queue>
#include <algorithm>

#ifndef _BINNODE_HPP_
#define _BINNODE_HPP_

#define BinNodePosi(T) BinNode<T>* /* 节点指针 */
#define stature(p) ((p) ? (p)->height : -1) /* 节点高度 */
typedef enum {RB_RED, RB_BLACK} RBColor;
/**
 * @brief BinNode状态与性质判断
 * 
 */
#define IsRoot(x) (!((x).parent))
#define IsLChild(x) (!(IsRoot(x)) && (&(x) == (x).parent->lc))
#define IsRChild(x) (!(IsRoot(x)) && (&(x) == (x).parent->rc))
#define HasParent(x) (!IsRoot(x))
#define HasLChild(x) ((x).lc)
#define HasRChild(x) ((x).rc)
#define HasChild(x) (HasLChild(x) || HasRChild(x))
#define HasBothChild(x) (HasLChild(x) && HasRChild(x))
#define IsLeaf(x) (!HasChild(x))

/**
 * @brief 与BinNode有特定关系的指针
 * 
 */
#define sibling(p) \
	(IsLChild(*(p)) ? (p)->parent->rc : (p)->parent->lc)

#define uncle(p) \
	(IsLChild(*((p)->parent)) ? (p)->parent->parent->rc : (p)->parent->parent->lc)

/* return a pointer to it from the parent */
#define FromParentTo(x) \
	(IsRoot(x) ? this->_root : (IsLChild(x) ? (x).parent->lc : (x).parent->rc))

template<typename T> struct BinNode {
	T data;
	BinNodePosi(T) parent;
	BinNodePosi(T) lc;
	BinNodePosi(T) rc;
	int height;
	int npl; /* Null path length */
	RBColor color;

	BinNode():
		parent(NULL), lc(NULL), rc(NULL), 
		height(0), npl(1), color(RB_RED) {}

	BinNode(T e, BinNodePosi(T) _p = NULL, BinNodePosi(T) _lc = NULL, BinNodePosi(T) _rc = NULL,
		int _h = 0, int _npl = 1, RBColor _c = RB_RED): 
			data(e), parent(_p), lc(_lc), rc(_rc),
			height(_h), npl(_npl), color(_c) {} 

	int size() const;
	BinNodePosi(T) insertAsLC(T const&);
	BinNodePosi(T) insertAsRC(T const&);
	BinNodePosi(T) succ();
	template<class VST> void travLevel(VST&);
	template<class VST> void travPre(VST&);
	template<class VST> void travIn(VST&);
	template<class VST> void travPost(VST&);

	bool operator<(const BinNode& rhs) const {
		return data < rhs.data;
	}
	bool operator==(const BinNode& rhs) const {
		return data == rhs.data;
	}
};

template<class T>
BinNodePosi(T) BinNode<T>::insertAsLC(T const& _data) {
	return lc = new BinNode(_data, this);
}

template<class T>
BinNodePosi(T) BinNode<T>::insertAsRC(T const& _data) {
	return rc = new BinNode(_data, this);
}

#include "BinNode_implement.hpp"

#endif